package LeetCode.month01.day17;

public class No300 {

    public int lengthOfLIS(int[] nums) {
        int len = 1;
        int[] dp = new int[nums.length+1];
        dp[len] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if(nums[i]>dp[len]) dp[++len] = nums[i];
            else{
                int l = 0,r = len,index = 0;
                while(l<=r){
                    int mid = l+(r-l)/2;
                    if(dp[mid]<nums[i]){
                        l=mid+1;
                        index= mid;
                    }else{
                        r=mid-1;
                    }
                }
                dp[index+1] = nums[i];
            }
        }
        return len;
    }


//    public int lengthOfLIS(int[] nums) {
//        if(nums.length==0) return 0;
//        int[] dp = new int[nums.length];
//        dp[0] = 1;
//        int max = 1;
//        for (int i = 1; i < nums.length; i++) {
//            dp[i]= 1;
//            for (int j = 0; j < i; j++) {
//                if(nums[j]<nums[i]&&dp[j]>=dp[i]){
//                    dp[i] = dp[j]+1;
//                }
//            }
//            if(dp[i]>max) max=dp[i];
//        }
//        return max;
//    }
}
